#include "Sort.h"

void SortTest01()
{
	int arr[] = { 5,1,10,4,9,2,7,8,3,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	InsertSort(arr, sz);
	PrintArr(arr, sz);
}
void SortTest02()
{
	int arr[] = { 5,1,10,4,9,2,7,8,3,6 };
	//int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	QuickSort(arr, sz);
	PrintArr(arr, sz);
}

void TestOp()
{
	srand((unsigned int)time(NULL));
	int n = 10000000;
	int* a1 = (int*)malloc(sizeof(int) * n);
	int* a2 = (int*)malloc(sizeof(int) * n);
	int* a3 = (int*)malloc(sizeof(int) * n);
	int* a4 = (int*)malloc(sizeof(int) * n);
	int* a5 = (int*)malloc(sizeof(int) * n);
	int* a6 = (int*)malloc(sizeof(int) * n);
	int* a7 = (int*)malloc(sizeof(int) * n);
	if (!a1 || !a2 || !a3 || !a4 || !a5 || !a6 || !a7) exit(1);
	for (int i = 0; i < n; i++)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
	}
	int begin1 = clock();
	//InsertSort(a1, n);
	int end1 = clock();

	int begin2 = clock();
	//BubbleSort(a2, n);
	int end2 = clock();

	int begin3 = clock();
	HeapSort(a3, n);
	int end3 = clock();

	int begin4 = clock();
	ShellSort(a4, n);
	int end4 = clock();

	int begin5 = clock();
	//SelectSort(a5, n);
	int end5 = clock();

	int begin6 = clock();
	QuickSort(a6, n);
	int end6 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("BubbleSort:%d\n", end2 - begin2);
	printf("HeapSort:%d\n", end3 - begin3);
	printf("ShellSort:%d\n", end4 - begin4);
	printf("SelectSort:%d\n", end5 - begin5);
	printf("QuickSort:%d\n", end6 - begin6);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
}

void insertSort(int* arr, int sz)
{
	for (int i = 0; i < sz - 1; i++)
	{
		//end指向已经排好序的最后一个数据的位置
		int end = i;
		//tmp保存正在排序的数据
		int tmp = *(arr + end + 1);
		while(end >= 0)
		{
			if (tmp < *(arr + end))
			{
				//往后挪
				*(arr + end + 1) = *(arr + end);
				end--;
			}
			else
				break;
		}
		*(arr + end + 1) = tmp;
	}
}

void shellSort(int* arr, int sz)
{
	int gap = 3;
	while (gap--)
	{
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < sz - gap; i += gap)
			{
				int end = i;
				int tmp = *(arr + end + gap);
				while (end >= 0)
				{
					if (*(arr + end) > tmp)
					{
						//往后挪
						*(arr + end + gap) = *(arr + end);
						end -= gap;
					}
					else
						break;
				}
				*(arr + end + gap) = tmp;
			}
		}
	}
}

void Test()
{
	int arr[] = { 5,1,10,4,9,2,7,8,3,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	shellSort(arr, sz);
	PrintArr(arr, sz);
}

/*
//找基准值
int _quickSort_(int* arr, int left, int right)
{
	//假设基准值为数组第一个元素,其实我也不知道,随便定的
	int keyi = left;
	//left指向基准值后面的数据
	left++;
	while (left <= right)//那么这个while循环是left<right还是left<=right
	{
		//right从右往左走找小
		while (left <= right && arr[right] > arr[keyi])
		{
			right--;
		}
		//left从左往右走找大
		while (left <= right && arr[left] < arr[keyi])
		{
			left++;
		}
		if (left <= right)
			//代码走到这就说明left找到了比基准值大的,right找到了比基准值小的,然后交换。
			Swap(arr + right--, arr + left++);
	}

	//交换right位置的值和keyi位置的值,让right位置的值成为基准值,前提是left小于right
	Swap(arr + right, arr + keyi);
	return right;
}

//快速排序的写法和前面的排序的参数不太一样。
void _quickSort(int* arr, int left, int right)
{
	//当left等于right的时候也就是说当前只有一个数据,所有没必要找基准值了
	if (left >= right)
	{
		return;
	}
	//[left,right] ---> 找基准值keyi
	int keyi = _quickSort_(arr, left, right);
	//递归左子序列:[left,keyi-1] - 基准值不一定是中间位置的数据
	_quickSort(arr, left, keyi - 1);
	//递归右子序列:[keyi+1,right]
	_quickSort(arr, keyi + 1, right);
}

void SortTest03()
{
	int arr[] = { 5,1,10,4,9,2,7,8,3,6 };
	//int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	_quickSort(arr,0, sz-1);
	PrintArr(arr, sz);
}
*/

int main()
{
	//SortTest02();
	TestOp();
	//Test();
	return 0;
}